1. Field of the Invention
The present invention relates to the field of microprocessors and, more particularly, to a technique of sorting signed numbers and finding absolute differences.
2. Prior Art
In the utilization of processors, microprocessors and computer systems, it is the practice to manipulate large amounts of data represented in various forms. For many operations, the data is generally in a scalar format where operations are performed on such scalar values. For example, an adding of two numerical values entails the loading of the two values in two registers and numerically (either in integer form or floating point form) adding the two numbers. In order to speed the execution of current and subsequent instructions, many processors now employ the use of pipe-lining stages to enhance processing speed of the processor. The use of various instructions which operate on two data elements are well-known in the art.
A different type of data representation is a format referred to as "Packed Data" format. In the packed data format, a number of data elements are now grouped together into a common bit string having a specified width. For example, a packed data string may have four individual data elements, each having a specified width. Furthermore as an example, a packed data format having 64 bits may be comprised of four 16-bit data elements. A significant advantage of having such a packed data format resides in the multiple operations which can be performed on the data string. Accordingly, with the noted example above, a packed add instruction can be invoked to add two packed data words (wherein each packed word is comprised of four data elements). In this packed addition, corresponding pairs of data elements of the two words are added. Unlike the scalar add operation, the packed add instruction in this instance would perform four different add operations (one for each pair of corresponding data elements) in parallel in response to a single instruction.
As can be appreciated, a separate set of packed instruction set would be required in order to operate on the packed data format, as well as providing the necessary operations for packing and unpacking the data. Generally, the specialized instruction set can be designed into a general purpose processor at low cost, because most of the circuitry dedicated to scalar operations can be reused. However, such a processor would have significant processing advantages when packed data operations can be used instead of singular data operations.
One area where packed data operations are susceptible for improving performance is in the manipulation of multimedia data. That is, video, graphic and sound data can be manipulated in packed format using packed instructions. A variety of functions can be solved or data rearranged based on the use of the packed instruction set. One such manipulation is the sorting of numbers to determine which number from a pair of numbers is greater (or lesser) in value. One example of such a comparison is to determine if a given value is above or below a threshold value. Another such operation is the solving of an absolute difference between a pair of numbers. Such absolute difference is used to calculate a L1 Norm, which represent the distance between two sets of data. It is used in recognition operations, specifically in speech and handwriting recognition and also used in some image recognition functions as well.
For example, when an absolute difference between two signed numbers is to be obtained, the following operation is implemented:
To solve ABS[X-Y],
If X&gt;Y, then ABS[X-Y]=X-Y,
else ABS[X-Y]=Y-X.
which operation, when using prior art techniques, requires a conditional branch to ensure that the smaller signed number is subtracted from the larger number. This conditional branching would need to be implemented for each pair of numbers.
The present invention on the other hand describes a scheme in which a plurality of packed data elements are operated on in parallel to sort the greater values from each pair of numbers into a data string and lesser values from each pair of numbers into another data string, so that the lesser numbers can be subtracted from the larger numbers in a packed format to obtain the absolute difference for each pair of numbers.